home *** CD-ROM | disk | FTP | other *** search
/ Ham Radio 2000 #2 / Ham Radio 2000 - Volume 2.iso / HAMV2 / ANTENNA / YAGIU112 / GA_LIB.C% < prev    next >
Encoding:
Text File  |  1995-08-16  |  7.2 KB  |  332 lines
  1. #include <string.h>
  2. #ifndef GCC
  3. #include <stdlib.h>
  4. #endif
  5. #include <values.h>
  6. #include <math.h>
  7. #include <sys/types.h>
  8. #ifdef i386
  9. #ifdef UNIX
  10. #include <time.h>
  11. #endif
  12. #elif
  13. #include <sys/time.h>
  14. #endif
  15.  
  16. #include <errno.h>
  17. #include "yagi.h"
  18.  
  19.  
  20.  
  21. typedef struct {
  22.     int parent1,parent2 ;
  23.     char *gene ;
  24.     double fitness ;
  25.     } GeneRecord ;
  26.  
  27.  
  28. int population_size=0 ;
  29. int gene_length=0 ;
  30. int elite=1 ;
  31. int ramp=0 ;
  32. int PRINT=1 ;
  33. double MX ; 
  34. /* double pmutate=0.4 ;
  35. double pcross=0.6 ;
  36. double psimplex=0.4 ;
  37. double ptrans=0.2 ; */
  38. double pmutate=0.1 ; 
  39. double pcross=0.9 ;
  40. double psimplex=0.5 ;
  41. double ptrans=0.03 ;
  42. extern int errno;
  43.  
  44. GeneRecord *Pop1=NULL,*Pop2=NULL ;
  45.  
  46. void setprobs(double pm,double pc,double ps,double pt)
  47. {
  48.     pmutate=pm ;
  49.     pcross=pc ;
  50.     psimplex=ps;
  51.     ptrans=pt ;
  52. }
  53.  
  54. int GA_Free(void) 
  55. {
  56.     int a ;
  57.     if (Pop1!=NULL) {
  58.         for(a=0 ; a<population_size ;a++)
  59.             if (Pop1[a].gene!=NULL) free(Pop1[a].gene) ;
  60.         free((char *) Pop1) ;
  61.     }
  62.     if (Pop2!=NULL) {
  63.         for(a=0 ; a<population_size ;a++)
  64.             if (Pop2[a].gene!=NULL) free(Pop2[a].gene) ;
  65.         free((char *) Pop2) ;
  66.     }
  67. }
  68.  
  69. int GA_Error(char *ErrorMsg) 
  70. {
  71.     int a ;
  72.     if (Pop1!=NULL) {
  73.         for(a=0 ; a<population_size ;a++)
  74.             if (Pop1[a].gene!=NULL) free(Pop1[a].gene) ;
  75.         free(Pop1) ;
  76.     }
  77.     if (Pop2!=NULL) {
  78.         for(a=0 ; a<population_size ;a++)
  79.             if (Pop2[a].gene!=NULL) free(Pop2[a].gene) ;
  80.         free(Pop2) ;
  81.     }
  82.     fprintf(stderr,"GA_LIB Error : %s \n\n",ErrorMsg) ;
  83.     exit(1) ;
  84. }       
  85.  
  86. double GetMax()
  87. {
  88.     return(MX) ;
  89. }
  90.  
  91. void SetPrint(int a)
  92. {
  93.     PRINT=a; 
  94. }
  95. void dump_pop1(FILE *fd,int generation,double max,double aver) 
  96. {
  97.     int a ;
  98.  
  99.     if (PRINT==0) return ;
  100.     fprintf(fd,"Current contents of population: generation %d\n",generation);
  101.     for(a=0 ; a<gene_length ; a++) fprintf(fd,"-");
  102.     fprintf(fd,"------------------\n");
  103.     fprintf(fd,"Par1 Par2 Fitness   Code\n");
  104.     for(a=0 ; a<population_size ; a++)
  105.         fprintf(fd,"%4d %4d %9.4f %s\n",Pop1[a].parent1,Pop1[a].parent2,Pop1[a].fitness,Pop1[a].gene);
  106.     fprintf(fd,"\n Maximum %9.4lf Average %9.4lf\n",max,aver);
  107.     for(a=0 ; a<gene_length ; a++) fprintf(fd,"-");
  108.     fprintf(fd,"------------------\n\n");
  109. }        
  110.  
  111. int Initialise(int PopSize, int GeneSize) 
  112. {
  113.     int a,b ;
  114.     char c[2] ;
  115.     
  116.     c[1]=0 ;
  117.  
  118.     /* srandom(time(&a)); */
  119.     ramp=0 ;
  120.     population_size=PopSize ;
  121.     gene_length=GeneSize+1 ;
  122.     /* limit population size */
  123.     if ((PopSize<20)||(PopSize>1000)) GA_Error("Bad parameters to Initialise") ;
  124.     /* Allocate memory for population 1 */
  125.     Pop1=(GeneRecord *)calloc(PopSize,sizeof(GeneRecord)) ;
  126.     /* Mem alloc error */
  127.     if (Pop1==NULL) GA_Error((char *)"Memory allocation for population 1") ;
  128.     /* Blank population array */
  129.     for (a=0 ; a<population_size ; a++) {
  130.         Pop1[a].gene=NULL ;
  131.         Pop1[a].parent1=0 ;
  132.         Pop1[a].parent2=0 ;
  133.         Pop1[a].fitness=0.0 ;
  134.     }
  135.     /* Allocate memory for genes */
  136.     for (a=0 ; a<population_size ; a++) 
  137.         if ((Pop1[a].gene=malloc(gene_length))==NULL) 
  138.             GA_Error("Cannot allocate gene in population 1");
  139.     /* Allocate memory for population 2 */
  140.     Pop2=(GeneRecord *)calloc(PopSize,sizeof(GeneRecord)) ;
  141.     /* Mem alloc error */
  142.     if (Pop2==NULL) GA_Error((char *)"Memory allocation for population 1") ;
  143.     /* Blank population array */
  144.     for (a=0 ; a<population_size ; a++) {
  145.         Pop2[a].gene=NULL ;
  146.         Pop2[a].parent1=0 ;
  147.         Pop2[a].parent2=0 ;
  148.         Pop2[a].fitness=0.0 ;
  149.     }
  150.     /* Allocate memory for genes */
  151.     for (a=0 ; a<population_size ; a++) 
  152.         if ((Pop2[a].gene=malloc(gene_length))==NULL) 
  153.             GA_Error("Cannot allocate gene in population 2");
  154.     /* Initialise genes */
  155.     for (a=0 ; a<population_size ; a++) {
  156.         for (b=0 ; b<GeneSize ; b++) 
  157.             /* Pop1[a].gene[b]=(char)(48+(randint()&1)) ;XXXXXXXX */
  158.             Pop1[a].gene[b]=(char)(48+(randint()&1)) ;
  159.         Pop1[a].gene[GeneSize]=0 ;
  160.     }
  161.  
  162. #ifdef DEBUG
  163.     if(errno)
  164.     {
  165.         fprintf(stderr,"Errno =%d in Initialise() of ga_lib.c\n", errno);
  166.         exit(1);
  167.     }
  168. #endif
  169.     return (0) ;
  170. }
  171.  
  172. void crossover(char *s1,char *s2)
  173. {
  174.     int point;
  175.     char duplic ;
  176.     
  177.     /* only works for strings of same length */
  178.     if (strlen(s1)!=strlen(s2)) GA_Error((char *)"Gene length mismatch for crossover") ;
  179.     /* choose a point and swap tails of strings */
  180.     for (point=(randint()%(strlen(s1)-2))+1 ; point <strlen(s1) ; point++)
  181.     {
  182.         duplic=s1[point] ;
  183.         s1[point]=s2[point] ;
  184.         s2[point]=duplic ;
  185.     } 
  186. }
  187.  
  188. void mutate(char *s1)
  189. {
  190.     /* flip a bit in at random point */
  191.     s1[randint()%strlen(s1)]^=1 ;
  192. }       
  193.  
  194. int ga_simplex(char *s1,char *s2, char *s3)
  195. {
  196.     int point ;
  197.     for (point=0 ; point <(strlen(s1)-1) ; point++ )
  198.         if (s1[point]==s2[point]) 
  199.             s3[point]=s1[point] ;
  200.         else
  201.             s3[point]=s3[point]^1 ;
  202. }
  203.  
  204. void swap(int *x,int *y)
  205. {
  206.     int t ;
  207.     t=*x ;
  208.     *x=*y ;
  209.     *y=t ;
  210. }       
  211.  
  212. void Sort() 
  213. {
  214.     GeneRecord T ;
  215.     int outer,inner,moved;
  216.     
  217.     for (outer=population_size-1; outer>0 ; outer--)
  218.     {
  219.         moved=0 ;
  220.         for (inner=0 ; inner<outer ; inner++)
  221.         {
  222.             if (Pop1[inner].fitness<Pop1[inner+1].fitness)
  223.             {
  224.                 memcpy((char *) &T,(char *) &Pop1[inner],sizeof(GeneRecord)) ;
  225.                 memcpy((char *) &Pop1[inner],(char *) &Pop1[inner+1],sizeof(GeneRecord)) ;
  226.                 memcpy((char *) &Pop1[inner+1],(char *) &T,sizeof(GeneRecord)) ;
  227.                 moved=1;
  228.             }
  229.         }
  230.         if (moved==0) break ;
  231.     }
  232. }
  233.     
  234. void transloc(char *gene) 
  235. {
  236.     int a,point,gene_size ;
  237.     char *dup;
  238.  
  239.     gene_size=gene_length-1 ;
  240.     point=randint()%gene_size ;
  241.     dup=strdup(gene) ;
  242.     for(a=0 ; a<gene_size ; a++) gene[a]=dup[(a+point)%gene_size] ;
  243.     free(dup);
  244. }
  245.     
  246. int Selection(FILE *fd, int gen)
  247. {
  248.     int a,b,c,select,d ;
  249.     double sigma,rd ;
  250.     GeneRecord *temp ;
  251.     double minfit,maxfit ;
  252.     FILE *tmp;
  253.     sigma=0.0 ;
  254.     minfit=MAXDOUBLE ; 
  255.     maxfit=-minfit ;
  256.     /* minfit=1e308; maxfit=-1e308; XXXXXXXXXXXXXXXXXXXXXX */
  257.     for(a=0 ; a<population_size ; a++ ) 
  258.     {
  259.         Pop1[a].fitness=Objective(Pop1[a].gene) ;
  260.         if (Pop1[a].fitness<minfit) minfit=Pop1[a].fitness ;
  261.         if (Pop1[a].fitness>maxfit) maxfit=Pop1[a].fitness ;
  262.         sigma+=Pop1[a].fitness ;
  263.     }
  264.     MX=maxfit ;
  265.     Sort() ;
  266.     dump_pop1(fd,gen,maxfit,sigma/population_size);
  267.     for(a=0 ; a<population_size ; a++ ) 
  268.     {
  269.         if(minfit!=maxfit)
  270.         {
  271.             Pop1[a].fitness=((Pop1[a].fitness-minfit)*99.0/(maxfit-minfit))+1.0 ;
  272.         }
  273.     }
  274.     ramp++ ;
  275.     sigma=0.0 ;
  276.     for(a=0 ; a<population_size ; a++ ) 
  277.         sigma+=Pop1[a].fitness ;
  278.     c=0 ;
  279.     for(a=0 ; a<population_size ; a++ )
  280.     {
  281.         b=(int) (Pop1[a].fitness*population_size/sigma) ;
  282.         for (d=0 ; d<b ; d++)
  283.             strcpy(Pop2[c++].gene,Pop1[a].gene) ;
  284.     }       
  285.     for(d=c ; d<population_size ; d++)
  286.     {
  287.             b=randint()%population_size ;
  288.             strcpy(Pop2[d].gene,Pop1[b].gene) ;
  289.     }
  290.     for(a=0 ; a<population_size ;a++)
  291.     {
  292.         if (randreal()<pmutate) mutate(Pop2[a].gene) ;
  293.         if (randreal()<ptrans) transloc(Pop2[a].gene) ;
  294.     }
  295.     temp=Pop1 ;
  296.     Pop1=Pop2 ;
  297.     Pop2=temp ;
  298.     for(a=2 ; a<population_size ; a+=2 )
  299.     {
  300.         b=randint()%population_size ;
  301.         c=randint()%population_size ;
  302.         strcpy(Pop2[a].gene,Pop1[b].gene);
  303.         strcpy(Pop2[a+1].gene,Pop1[c].gene);
  304.         if (randreal()<pcross)
  305.         {
  306.             crossover(Pop2[a].gene,Pop2[a+1].gene) ;
  307.             Pop2[a].parent2=Pop2[a+1].parent1 ;
  308.             Pop2[a+1].parent2=Pop2[a].parent1 ;
  309.         } else {
  310.             Pop2[a].parent2=Pop2[a].parent1 ;
  311.             Pop2[a+1].parent2=Pop2[a+1].parent1 ;
  312.         }
  313.     }
  314.     if (randreal()<psimplex) {
  315.         a=randint()%population_size ;   
  316.         b=randint()%population_size ;   
  317.         c=randint()%population_size ;   
  318.         if (Pop1[a].fitness<Pop1[b].fitness) 
  319.             swap(&a,&b) ;
  320.         if (Pop1[b].fitness<Pop1[c].fitness) 
  321.             swap(&b,&c) ;
  322.         if (Pop1[a].fitness<Pop1[b].fitness) 
  323.             swap(&a,&b) ;
  324.         ga_simplex(Pop1[a].gene,Pop1[b].gene,Pop2[c].gene);
  325.     }
  326.     temp=Pop1 ;
  327.     Pop1=Pop2 ;
  328.     Pop2=temp ;
  329.     return 0 ;
  330. }
  331.                 
  332.